package shortestPath;

public class DijkstraLimonQueue {
	public static long ShortestPathTo(int[][] matrix, boolean showAnswer) {
		long startTime = System.currentTimeMillis();
		
		int max = 1<<29, len = matrix.length, temp, best, x=0, y=0, queueSize=1, i, j, bestP=0;
		int[][] dist = new int[len][len];
		boolean[][] visited = new boolean[len][len];
		
		for(i=0; i<dist.length; i++)
			for(j=0; j<dist[0].length; j++) dist[i][j] = max;
		dist[0][0] = matrix[0][0];
		
		int[][] queue = new int[len<<3][2];
		queue[0]=new int[]{0, 0};
		
		while(!visited[len-1][len-1]){
			best = max;
			for(int p=0; p<queueSize; p++){
				i = queue[p][0];
				j = queue[p][1];
				if(dist[i][j] < best){
					best = dist[i][j];
					x=j;
					y=i;
					bestP=p;
				}
			}
			
			queue[bestP] = queue[--queueSize];
			
			if(y>0 && (temp=best + matrix[y-1][x]) < dist[y-1][x]) {
				dist[y-1][x] = temp;
				queue[queueSize++] = new int[]{y-1, x};
			}
			if(y<len-1 && (temp=best + matrix[y+1][x]) < dist[y+1][x]) {
				dist[y+1][x] = temp;			
				queue[queueSize++] = new int[]{y+1, x};
				}
			if(x>0 && (temp=best + matrix[y][x-1]) < dist[y][x-1]) {
				dist[y][x-1] = temp;
				queue[queueSize++] = new int[]{y, x-1};
			}
			if(x<len-1 && (temp=best + matrix[y][x+1]) < dist[y][x+1]) {
				dist[y][x+1] = temp;
				queue[queueSize++] = new int[]{y, x+1};
			}
			
			visited[y][x] = true;
		}
		
		if(showAnswer) System.out.println(dist[len-1][len-1]);	
		return (System.currentTimeMillis()-startTime);
	}
}
